//有效的数独(medium) : https://leetcode.cn/problems/valid-sudoku/description/
class Solution {
public:
    bool row[9][10];    
    bool col[9][10];   //如果row[9][8]=1:则表示第九行含有8号元素
    bool grid[3][3][10];    // grid[3][3][10]：  [3][3]:表示将9宫格分成了9分  [8]:和row[9][8]的意思相同
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    int x=board[i][j]-'0';
                    if(row[i][x]!=false||col[j][x]!=false||grid[i/3][j/3][x]!=false)
                    {
                        return false;
                    }
                    row[i][x]=col[j][x]=grid[i/3][j/3][x]=true;
                }
            }
        }
        return true;
    }
};

//解数独(hard) : https://leetcode.cn/problems/sudoku-solver/description/
class Solution {
public:
    bool row[9][10],col[9][10];
    bool grid[3][3][10];
    void solveSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    char ch=board[i][j];
                    row[i][ch-'0']=col[j][ch-'0']=grid[i/3][j/3][ch-'0']=true;
                }
            }
        }
        dfs(board);
    }
    bool dfs(vector<vector<char>>& board)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]=='.')  //为空格
                {
                //开始填充
                for(int num=1;num<=9;num++)  //填充的数字
                {
                    if(!row[i][num]&&!col[j][num]&&!grid[i/3][j/3][num])
                    {
                        board[i][j]=num+'0';  
                        row[i][num]=col[j][num]=grid[i/3][j/3][num]=true;
                        //如果为true,说明下一个数，下下个数都行，即全部都行
                        //如果为false,说明选这个数的话，下一个数字不行，那么这个数重选
                        if(dfs(board)==true)   return true;  
                        //恢复现场
                        board[i][j]='.';  
                        row[i][num]=col[j][num]=grid[i/3][j/3][num]=false;
                    }
                }
                //1-9都选完了，都没选到合适的，说明这个数不行
                return false;
                }
            }
            
        }
        return true;
    }
};